package com.aikon.wht.paoshan.alg;

/**
 * 回溯算法
 *
 * @author WANGHAITAO273
 */
public class PaoshanOfHuisu {

    /**
     * 01背包
     * <p>
     * 假设有n件物品，分别重w[i]，分别价值p[i]。现有可承重c的背包，要求如何选择物品放入背包总价值最大。
     */
    public static class Pack {

        public static void main(String[] args) {
            int n = 5;
            int[] w = new int[]{1, 2, 3, 4, 5};
            int[] p = new int[]{5, 4, 3, 2, 1};
            int c = 10;

            int r = calc(0, n, w[0], p[0], w, p);
            System.out.println(r);

        }

        public static int calc(int i, int n, int cw, int cp, int[] w, int[] p) {
            cw += cw;
            cp += cp;
            if (i < n) {
                calc(i + 1, n, 0, 0, w, p);
                calc(i + 1, n, w[i], p[i], w, p);
            }
            return cp;
        }


    }
}